`:top

The `!winnow algorithm`!`:cite-ref-littlestone88-1-0[`F5bf`_`[1`#cite-note-littlestone88-1]`_`f] is a technique from `F33f`_`[machine learning`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Machine_learning]`_`f for learning a `F33f`_`[linear classifier`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linear_classifier]`_`f from labeled examples. It is very similar to the `F33f`_`[perceptron algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Perceptron]`_`f. However, the perceptron algorithm uses an additive weight-update scheme, while Winnow uses a `F33f`_`[multiplicative scheme`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multiplicative_Weight_Update_Method]`_`f that allows it to perform much better when many dimensions are irrelevant (hence its name `F33f`_`[winnow`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Winnowing]`_`f). It is a simple algorithm that scales well to high-dimensional data. During training, Winnow is shown a sequence of positive and negative examples. From these it learns a decision `F33f`_`[hyperplane`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hyperplane]`_`f that can then be used to label novel examples as positive or negative. The algorithm can also be used in the `F33f`_`[online learning`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Online_machine_learning]`_`f setting, where the learning and the classification phase are not clearly separated.

>>Contents

• `F0af`_`[Algorithm`#algorithm]`_`f

• `F0af`_`[Mistake bounds`#mistake-bounds]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Algorithm

The basic algorithm, Winnow1, is as follows. The instance space is X = { 0 , 1 } n {\\displaystyle X=\\{0,1\\}^{n}} , that is, each instance is described as a set of `F33f`_`[Boolean-valued`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boolean-valued]`_`f `F33f`_`[features`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Features_(pattern_recognition)]`_`f. The algorithm maintains non-negative weights w i {\\displaystyle w_{i}} for i ∈ ∈ { 1 , … … , n } {\\displaystyle i\\in \\{1,\\ldots ,n\\}} , which are initially set to 1, one weight for each feature. When the learner is given an example ( x 1 , … … , x n ) {\\displaystyle (x_{1},\\ldots ,x_{n})} , it applies the typical prediction rule for linear classifiers:

• `!If`! ∑ ∑ i = 1 n w i x i > Θ Θ {\\displaystyle \\sum _{i=1}^{n}w_{i}x_{i}>\\Theta } , `!then`! predict 1

• `!Otherwise`! predict 0

Here Θ Θ {\\displaystyle \\Theta } is a real number that is called the `*threshold`*. Together with the weights, the threshold defines a dividing hyperplane in the instance space. Good bounds are obtained if Θ Θ = n / 2 {\\displaystyle \\Theta =n/2} (see below).

For each example with which it is presented, the learner applies the following update rule:

• If an example is correctly classified, do nothing.

• If an example is predicted incorrectly and the correct result was 0, for each feature x i = 1 {\\displaystyle x_{i}=1} , the corresponding weight w i {\\displaystyle w_{i}} is set to 0 (demotion step). ∀ ∀ x i = 1 , w i = 0 {\\displaystyle \\forall x_{i}=1,w_{i}=0}

• If an example is predicted incorrectly and the correct result was 1, for each feature x i = 1 {\\displaystyle x_{i}=1} , the corresponding weight w i {\\displaystyle w_{i}} multiplied by α(promotion step). ∀ ∀ x i = 1 , w i = α α w i {\\displaystyle \\forall x_{i}=1,w_{i}=\\alpha w_{i}}

A typical value for α is 2.

There are many variations to this basic approach. `*Winnow2`*`:cite-ref-littlestone88-1-1[`F5bf`_`[1`#cite-note-littlestone88-1]`_`f] is similar except that in the demotion step the weights are divided by α instead of being set to 0. `*Balanced Winnow`* maintains two sets of weights, and thus two hyperplanes. This can then be generalized for `F33f`_`[multi-label classification`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multi-label_classification]`_`f.

>>Mistake bounds

In certain circumstances, it can be shown that the number of mistakes Winnow makes as it learns has an `F33f`_`[upper bound`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Upper_and_lower_bounds]`_`f that is independent of the number of instances with which it is presented. If the Winnow1 algorithm uses α α > 1 {\\displaystyle \\alpha >1} and Θ Θ ≥ ≥ 1 / α α {\\displaystyle \\Theta \\geq 1/\\alpha } on a target function that is a k {\\displaystyle k} -literal monotone disjunction given by f ( x 1 , … … , x n ) = x i 1 ∪ ∪ ⋯ ⋯ ∪ ∪ x i k {\\displaystyle f(x_{1},\\ldots ,x_{n})=x_{i_{1}}\\cup \\cdots \\cup x_{i_{k}}} , then for any sequence of instances the total number of mistakes is bounded by: α α k ( log α α ⁡ ⁡ Θ Θ + 1 ) + n Θ Θ {\\displaystyle \\alpha k(\\log _{\\alpha }\\Theta +1)+{\\frac {n}{\\Theta }}} .`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

>>References

`:cite-note-littlestone88-1`!1.`! `F0af`_`[↑`#cite-ref-littlestone88-1-0]`_`f Nick Littlestone (1988). "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm", `*Machine Learning`* 285–318(2).

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f Nick Littlestone (1989). "Mistake bounds and logarithmic linear-threshold learning algorithms". Technical report UCSC-CRL-89-11, University of California, Santa Cruz.

`c`F0af`_`[↑ Back to top`#top]`_`f`a